package algorithm.swordoff;

/**
 * 数组中出现此处超过一半的数字
 * 摩尔投票法
 */

public class SQ39 {
    public int majorityElement(int[] nums) {
        // 候选数字,票数
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candidate) count++;
            else if (count-1 >= 0) count--;
            else candidate = nums[i];
        }
        return candidate;
    }
}
